#include <iostream>
using namespace std;

typedef struct node
{
	int data;
	node *next;
} node, *LinkStack;

//创建空栈
LinkStack CreateNULLStack(LinkStack &S)
{
	S = (LinkStack)malloc(sizeof(node));
	if (nullptr == S)
	{
		return nullptr;
	}
	S->data = 0;
	S->next = nullptr;
	return S;
}

//栈的插入函数
LinkStack Push(LinkStack &S, int data)
{
	if (S == nullptr)
	{
		return NULL;
	}
	LinkStack p = NULL;
	p = (LinkStack)malloc(sizeof(node));
	if (p == nullptr)
	{
		return S;
	}
	if (S->next == nullptr)
	{
		p->next = NULL;
	}
	else
	{
		p->next = S->next;
	}
	p->data = data;
	S->next = p;
	return S; //栈顶
}

//出栈函数
node Pop(LinkStack &S)
{
	node temp;
	temp.data = 0;
	temp.next = NULL;
	if (S == nullptr)
	{
		return temp;
	}
	temp = *S;
	if (S->next == NULL)
	{
		return temp;
	}
	LinkStack p = S->next;
	S->next = S->next->next;
	temp = *p;
	free(p);
	p = nullptr;
	return temp;
}

//双栈实现队列的入队函数
LinkStack StackToQueuPush(LinkStack &S, int data)
{
	node n;
	LinkStack S1 = NULL;
	CreateNULLStack(S1);
	while (S->next != nullptr)
	{
		n = Pop(S);
		Push(S1, n.data);
	}
	Push(S1, data);
	while (S1->next != NULL)
	{
		n = Pop(S1);
		Push(S, n.data);
	}
	return S;
}

int main()
{

	system("pause");
	return 0;
}
